package history

// 非降序的数组，找到第一个比目标值大的数字，返回对应的下标
// 1.二分查找
func searchFirstBiggerVal(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	if nums[0] > target {
		return 0
	}
	if nums[len(nums)-1] <= target {
		return -1
	}
	var leftIdx = 0
	var rightIdx = len(nums) - 1
	for leftIdx <= rightIdx {
		var midIdx = leftIdx + (rightIdx-leftIdx)/2
		if nums[midIdx] == target {
			leftIdx = midIdx + 1
		} else if nums[midIdx] > target {
			if nums[midIdx-1] <= target {
				return midIdx
			}
			rightIdx = midIdx - 1
		} else {
			//nums[midIdx] < target
			if nums[midIdx+1] > target {
				return midIdx + 1
			}
			leftIdx = midIdx + 1
		}
	}
	return -1
}
